package leetcodev1.数组;

import java.util.ArrayList;
import java.util.List;

public class LeetCode39 {

    //无重复元素 代表所有解都是唯一解
    //递归可以解这道题 选自己和不选自己
    //超出内存限制
    private List<List<Integer>> ret = new ArrayList<>();

    public List<List<Integer>> combinationSum1(int[] candidates, int target) {
        findRet(candidates, target, 0, new ArrayList<>());
        return this.ret;
    }

    //顺序递归遍历所有结果
    //但是缓存了所有
    private void findRet(int[] candidates, int target, int index, ArrayList<Integer> route) {
        if (target == 0) {
            this.ret.add(route);
            return;
        }

        if (index >= candidates.length) {
            return;
        }

        //选自己
        ArrayList<Integer> tmp = new ArrayList<>(route);
        tmp.add(candidates[index]);
        findRet(candidates, target - candidates[index], index, tmp);
        //不选自己
        findRet(candidates, target, index + 1, new ArrayList<>(route));
    }

    //每个数的个数取值[0,target/num]
    //类似0-n背包问题（唯一解） 本题要求多个解
    //使用回溯算法
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, target, 0, new ArrayList<>());
        return this.ret;
    }

    //通过排序可以减枝
    private void dfs(int[] candidates, int target, int index, ArrayList<Integer> route) {
        if (target == 0) {
            this.ret.add(new ArrayList<>(route));//只复制结果 不复制中间过程
            return;
        }

        if (index >= candidates.length) {
            return;
        }

        //跳过当前元素
        dfs(candidates, target, index + 1, route);

        //选择当前元素
        if (target - candidates[index] >= 0) {
            //选择 前进一步
            route.add(candidates[index]);//增加元素
            //通过合理的减枝减少运行次数
            dfs(candidates, target - candidates[index], index, route);//理解关键
            //回溯 后退一步
            route.remove(route.size() - 1);//删除元素 回溯 保证中间状态的一致
        }

        //运行到这里的时候需要保证route进来和返回的是一致的
        //回溯需要保证中间的状态的一致
    }
}
